4、方格分割
题目 方格分割
思路分析
两部分是围绕中心点对称的
想法是 用1表示一种颜色 0表示另一种颜色 枚举所有的排列情况
然后找到所有应该对称的下标组 对他们进行判断 如果发现某位置的对应位置不是相反 就直接continue
如果所有对称位置都符合01相反 就说明是一个可行方案
a[i][j]应该要与a[7-i][7-j]对称
但是不好对每个方格放01进行枚举
想了一下 可以转换成一维 用二进制数来枚举
因为二进制数每一位都是0或1 那么从0枚举到2^36 就可以考虑到所有的排列组合
看某个方案是否满足 只需要看某一位 和它对应的那一位为是否不一样即可
对应关系如下：
然后实际上二进制是从第0位开始的 所以关系应该是 i：36-i
所以得到以下代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long cnt=0;
for(long long i=0;i<(1LL<<36);i++){
bool success=true;
for(int d=0;d<18;d++){
long long curd = (i >> d) & 1LL;
long long backd = (i >> (35 - d)) & 1LL;
if(curd==backd){
success=false;
break;
}
}
if(success) cnt++;
}
cout<<cnt/4;
return 0;
}
看似很巧妙 实际……
由于\(2^{36}\) 的数量级极其庞大（超过687亿），即便每秒处理数百万个模式的速度运行,完成整个枚举也将花费几个小时到几天不等……
（把笔记本放那里跑了 看看3.5小时能不能出结果hh）
这题正解是用dfs
因为涉及到了方格图和方法数
因为中心对称 所以只需要考虑一边的所有组合 用dfs可以考虑到所有的情况 在往某方向走的时候 它的对应的点也要相应被标记 如果发现对应的点已经被标记过了 就说明这条路径不成立 直接回溯考虑其他路径
其实和刚才的枚举思路应该是差不多的 都是枚举一半的所有组合情况 看对面状态 一旦发现不一样就找下一个 但是因为dfs的减枝是比较强大的 即发现某个点不可行了 所有要经过该点的路径就都被剪去了 显然二进制枚举的方式无法做到这点 即使一发现某位不一样就break 也会浪费很多时间
DFS的剪枝效果
即时剪枝：在DFS中，一旦确定某条路径不可能满足条件（如违反了对称性），就会立即停止进一步探索这条路径，回溯到上一个决策点尝试其他选项。这种即时剪枝意味着大量潜在的无效路径根本不会被探索。
避免重复工作：通过在探索过程中记录哪些路径已经被证明是无效的，DFS避免了重复检查这些路径，进一步提高了效率。
二进制枚举的局限
盲目枚举：尽管二进制枚举试图通过只检查一半的位来减少工作量，但它本质上仍然是一种盲目的方法，因为它必须生成并检查每个可能的组合。在发现某个组合不满足条件后，它不能利用这个信息来避免生成其他类似的、同样无效的组合。
无法有效剪枝：即使在检测到对称位不匹配时立即停止，每次循环仍然从头开始，为每个可能的组合分配时间，这导致了大量的无效计算。
思路：
从网格的中心点开始。
向四个方向探索，每次探索时同时标记当前点和对称点。
如果探索到边界，则认为找到了一种有效的分割方式。
由于是沿着边界分割，所以实际上探索的是网格中的点，而不是单元格。
看来有必要补一下dfs的部分了
问题变成了 从中心点开始 找到一条走到边界 的路径 另一半是完全对称的
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=7;//0~6
bool st[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int res=0;
int n;
bool isVaild(int x,int y){
return x>=0 && x<=N-1 && y>=0 && y<=N-1 && !st[x][y];
}
void dfs(int x,int y){
if(x==0 || x==n || y==0 || y==n){
res++;
return;
}
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(isVaild(nx,ny) && isVaild(n-nx,n-ny)){
st[nx][ny]=st[n-nx][n-ny]=true;
dfs(nx,ny);
st[nx][ny]=st[n-nx][n-ny]=false;//该点可以走多次 需要回溯
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
n=N-1;
st[n/2][n/2]=true;
dfs(n/2,n/2);
cout<<res/4<<endl;
return 0;
}
💬 评论